package com.zhugang.week13.sort;

/**
 * @program algorithms
 * @description: MergeSort
 * @author: chanzhugang
 * @create: 2022/10/18 00:51
 */
public class MergeSort {

    /**
     * 归并排序
     *
     * @param arr
     * @param n
     */
    public void mergeSort(int[] arr, int n) {
        // 递归拆分成两个排序的数组； 合并两个排序数组为一个大数组
        mergeSort_(arr, 0, n - 1);
    }

    private void mergeSort_(int[] arr, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = p + (r - p) / 2;
        mergeSort_(arr, p, q);
        mergeSort_(arr, q + 1, r);

        merge(arr, p, q, r);
    }

    private void merge(int[] arr, int p, int q, int r) {
        // 合并两个有序数组：双指针
        int i = p;
        int j = q + 1;
        int[] temp = new int[r - p + 1];
        int k = 0;
        while (i <= q && j <= r) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 其中一个数组遍历完了
        while (i <= q) {
            temp[k++] = arr[i++];
        }
        while (j <= r) {
            temp[k++] = arr[j++];
        }
        // 拷贝到原数组
        for (int l = 0; l <= r - p; l++) {
            arr[p + l] = temp[l];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] arr = new int[]{5, 3, 1, 4, 2};
        mergeSort.mergeSort(arr, arr.length);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}